#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int solve_k_stairs(int n)
{
	if (1 == n)
	{
		return 1;
	}
	else if (2 == n)
	{
		return 2;
	}
	else if (3 == n)
	{
		return 4;
	}
	else
	{
		return solve_k_stairs(n - 3) + solve_k_stairs(n - 2) + solve_k_stairs(n - 1);
	}
}

// 1 1 1 1 1		*1
// 1 1 1 2			*4
// 1 3 1			*3
// 2 3				*2
// 2 2 1			*3
//					=13
// 
// So 7+4+2 = 13
// 
// 求solve(4)
// 1 1 1 1			*1
// 1 2 1			*3
// 2 2				*2 
// 3 1				*1

// 功能类似于哈希表的数组
// 主要是为了减小空间复杂度，避免重复计算

int kogeup_solve(int n)
{
	// 可以不需要递归那么多层
	// 哈希表是王道
	// 但是冲突解决和手写哈希函数其实没有那么神奇
	int arr[100000] = { 0 };

	arr[0] = 0;
	arr[1] = 1;
	arr[2] = 2;
	arr[3] = 4;

	for (int i = 4; i <= n; i++)
	{
		arr[i] = arr[i - 3] + arr[i - 2] + arr[i - 1];
	}

	return arr[n];
}
